// https://www.lintcode.com/problem/insert-interval/

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: Sorted interval list.
     * @param newInterval: new interval.
     * @return: A new interval list.
     */
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        // write your code here
        List<Interval> ret = new ArrayList<>();
        int i = 0;
        while (i < intervals.size()) {
            if (intervals.get(i).start > newInterval.start) {
                break;
            }
            ++i;
        }
        int start = 0;
        if (i > 0) {
            for (int j = 0; j < i; ++j) {
                ret.add(intervals.get(j));
            }
            intervals.set(i - 1, newInterval); // 准备处理合并
            start = i - 1;
        }
        else {
            ret.add(newInterval);
        }
        for (i = start; i < intervals.size(); ++i) {
            int last = ret.size() - 1;
            Interval iv = intervals.get(i);
            if ((iv.start >= ret.get(last).start) && (iv.start <= ret.get(last).end)) {
                if (iv.end > ret.get(last).end) {
                    ret.get(last).end = iv.end;
                }
            } else {
                ret.add(iv);
            }
        }
        return ret;
    }
}